package interview.threesum;

import java.util.ArrayList;
import java.util.Arrays;

public class ThreeSum {
	public int threesumDummy(int[] num) {
		return 0;
	}
	
	public ArrayList<ArrayList<Integer>> threesum(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> tmp;
		Arrays.sort(num);
		if (num.length < 3 || num[0] > 0 || num[num.length - 1] < 0) {
			return result;
		}

		int head = 0;
		int tail = num.length - 1;
		while (num[head] < 0 && num[tail - 1] >= 0) {
			int tmpsum = num[head] + num[tail];
			if (tmpsum > 0) {
				tail--;
			} else {
				int tmptail = tail - 1;
				while (num[tmptail] >= 0) {
					if (tmpsum + num[tmptail] == 0) {
						tmp = new ArrayList<Integer>();
						tmp.add(num[head]);
						tmp.add(num[tmptail]);
						tmp.add(num[tail]);
						result.add(tmp);
					}
					tmptail--;
					while(num[tmptail] == num[tmptail + 1]) {
						tmptail--;
					}
				}
				head++;
				while(num[head] == num[head - 1]) {
					head++;
				}
			}
		}

		head = 0;
		tail = num.length - 1;
		while (num[tail] >= 0 && num[head + 1] <= 0) {
			int tmpsum = num[head] + num[tail];
			if (tmpsum < 0) {
				head++;
			} else {
				int tmphead = head + 1;
				while (num[tmphead] <= 0) {
					if (tmpsum + num[tmphead] == 0 && (num[head] == 0 || tmpsum != 0)) {
						tmp = new ArrayList<Integer>();
						tmp.add(num[head]);
						tmp.add(num[tmphead]);
						tmp.add(num[tail]);
						result.add(tmp);
					}
					tmphead++;
					while(num[tmphead] == num[tmphead - 1]) {
						tmphead++;
					}
				}
				tail--;
				while(num[tail] == num[tail + 1]) {
					tail--;
				}
			}
		}
		
		for(ArrayList<Integer> al : result) {
			for(int i : al) {
				System.out.print(i + " ");
			}
			System.out.println();
		}

		return result;
	}

	public ArrayList<ArrayList<Integer>> threesum2(int[] num) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if(num.length < 3) {
			return result;
		}
		
		Arrays.sort(num);
		for(int i = 0; i < num.length - 2; i++) {
			if(i > 0 && num[i - 1] == num[i]) {
				continue;
			}
			
			int j = i + 1;
			int k = num.length - 1;
			while(j < k) {
				int sum = num[i] + num[j] + num[k];
				if(sum < 0) {
					j++;
				} else if (sum > 0) {
					k--;
				} else {
					ArrayList<Integer> candidate = new ArrayList<Integer>();
					candidate.add(num[i]);
					candidate.add(num[j]);
					candidate.add(num[k]);
					result.add(candidate);
					
					j++;
					while(j <= k && num[j - 1] == num[j]) {
						j++;
					}
					
					k--;
					while(k >= j && num[k + 1] == num[k]) {
						k--;
					}

				}
			}
		}
		
		return result;
	}
}
